package com.fr.lintcode;

public class Q1686 {
	/**
	 * @param n: The number of bricks.
	 * @param b: The number of boots.
	 * @param f: The thickness of snow on bricks.
	 * @param s: The boots maximum depth of walking.
	 * @param d: The boots maximum length of walking.
	 * @return: Return the minimum number of boots you should discard.
	 */
	public int getMinimumNumOfBoots(int n, int b, int[] f, int[] s, int[] d) {
		// Write your code here.
		if (f == null || s == null || d == null) {
			return 0;
		}
		int[] dp = new int[b + 1];
		for (int j = 1; j <= b; j++) {
			boolean reachNext = false;
			int max = 0;
			for (int i = 1; i < d[j - 1]; i++) {
				if(dp[j - 1] + i >= n ) {
					break;
				}
				if (s[0] > f[dp[j - 1] + i]) {
					max = i;
					reachNext = true;
				}
			}
			if (reachNext) {
				dp[j - 1] = dp[j - 1] + max;
			} else {
				dp[j] = Math.max(dp[j - 1], dp[j - 1]);
				continue;
			}
			if (dp[j] >= n) {
				break;
			}
		}
		for (int i = 1; i <= b; i++) {
			if (dp[i] >= n) {
				return i - 1;
			}
		}
		return 0;
	}

}
